package main

import (
	"sort"
)

// 首先要求是 1.攻击 2.防御都严格大于的，才是弱角色
// 官方题解单调栈的思路是，先按照 1.攻击 升序排序，那么就能保证，后面的元素，攻击值都要大于或者等于前面的元素
// 之后问题就只剩下了 2.防御值 要求后面元素大于前面元素， 就能保证产生 弱角色。
// 那么问题抽象出来之后，就变成了： 求每个元素右边第一个大于自己的！
// 这是个典型的单调栈解决问题。

func numberOfWeakCharacters(properties [][]int) (ans int) {
	// 1. 首先自定义排序，按照攻击值升序排序
	sort.Slice(properties, func(i, j int) bool {
		p, q := properties[i], properties[j]
		return p[0] < q[0] || p[0] == q[0] && p[1] > q[1]
	})
	// 2. 定义队列，实现：求每个元素右边第一个大于自己的 功能
	st := []int{}
	for _, p := range properties {
		for len(st) > 0 && st[len(st)-1] < p[1] {
			st = st[:len(st)-1]
			ans++
		}
		st = append(st, p[1])
	}
	return
}
